// 键盘输入广义表形式输出的二叉树字符串，例如输入  A(B(D,E),C(,F)))
// 按照输入的字符规律建立二叉树，提示使用栈作为辅助。

// 二叉树中序遍历的次序输出。

// 输入：A(B(D,E),C(,F))

// 输出：二叉树中序遍历:D B E A C F

#include <iostream>
#include <stdio.h>
#include <cstring>
#define MAXSIZE 200
 
using namespace std;
typedef struct BiTnode 
{
	char data;
	struct BiTnode *lchild, *rchild;
} *BiTree, BitNode;
int createBiTree(BiTree &T, char *str)
{
	BiTree S[MAXSIZE], p = NULL;
	int top = 0, k = 0, j = 0;//k=1表示左孩子，k=2表示右孩子
	char ch;
	T = NULL;
	ch = str[j];
	while (ch!='\0')//ch一个一个读取广义表字符串
	{
		switch (ch)
		{
		case '('://遇到左括号，接下来读取的元素可能是左孩子，将双亲结点p入栈，标志k为1
			S[top++] = p; // S[top] = p;top++;
			k = 1;
			break;
		case ',':// 遇到逗号，下一个读取的元素是右孩子，标志k为2
			k = 2;
			break;
		case ')'://遇到右括号，表明当前层读取结束，回退到上一层，上一层的栈元素将成为新的双亲结点
			top--;
			break;
		default://遇到字符，创建新结点，将该结点插入对应的子树中,k=1表示左子树，k=2表示右子树
			p = new BitNode;
			p->data = ch;
			p->lchild = p->rchild = NULL;
			if (T==NULL)
			{
				T = p;
			} 
			else
			{
				switch (k)
				{
				case 1:
					S[top - 1]->lchild = p;
					break;
				case 2:
					S[top - 1]->rchild = p;
					break;
				}
			}
			break;
		}
		ch = str[++j];
	}
 
	return 1;
}
 
void output(BiTree T)//中序输出树
{
    if(T)
    {
        output(T->lchild);//先左孩子
        cout << T->data<<' ';//中序
        output(T->rchild);//后右孩子   
    }
}

int main()
{
	int n;
	char  str[MAXSIZE];
	BiTree T;
    gets(str);
    n = createBiTree(T, str);
	if (n==1)
	{
		cout << "二叉树中序遍历:";
        output(T);
    } 
    return 0;
}


/*不用建立二叉树

#include <iostream>
#include <string.h>
#define MAXSIZE 100//栈中能达到的最大容量
using namespace std;

typedef struct Node
{
    char data[MAXSIZE];
}Seqstack;

void Seqstackpush(Seqstack &S,int i,char s1[],int top)
{
    S.data[top]=s1[i];
}

void Seqstackpop(Seqstack &S,int top)
{
    cout<<S.data[top]<<' ';
}

int main()
{
    char s1[100];
    Seqstack S;
    int top=-1,m,i;
    gets(s1);
    m=strlen(s1);
    cout<<"二叉树中序遍历:";
    for(i=0;i<m;i++)
    {
        if(s1[i]=='(')
        {
            if(s1[i-1]!=S.data[top])
            {
                top++;
                Seqstackpush(S, i - 1, s1, top); // 父节点入栈
            }
        }
        else if(s1[i]==',')//左子树读取完
        {
            continue;
        }
        else if(s1[i]==')')
        {
            if(s1[i-1]=='(')//即：()
            {
                Seqstackpop(S, top);//父节点出栈
                top--;
            }
            else if(s1[i-1]==',')//即: ,)
            {
                if(s1[i-2]=='(')//即：(,)
                {
                    Seqstackpop(S, top);//父节点出栈
                    top--;
                }
                else//即：(X,)
                {
                    Seqstackpop(S, top);//左子树剩余元素出栈
                    top--;
                    Seqstackpop(S, top);//父节点出栈
                    top--;
                }
            }
            else if(s1[i-1]==')')//即：))
            {
                continue;
            }
            else//即: X)
            {
                if(s1[i-2]=='(')//即：(X)
                {
                    Seqstackpop(S, top);//左子树剩余元素出栈
                    top--;
                    Seqstackpop(S, top);//父节点出栈
                    top--;
                }
                else//即：(,X)
                {
                    Seqstackpop(S, top);//右子树出栈
                    top--;
                }
            }
        }
        else//结点X
        {//检查结点的前一个元素确定结点位置
            if(s1[i-1]=='(')//结点为左子树
            {
                top++;
                Seqstackpush(S, i , s1, top); // 左子树入栈
            }
            else if(s1[i-1]==',')//结点为右子树
            {
                if(s1[i-2]=='(')//左子树为空，即：(,X
                {
                    Seqstackpop(S, top);//父节点出栈
                    Seqstackpush(S, i , s1, top);//右子树入栈
                }
                else
                {
                    if(s1[i-2]==')')//即：(A(B,C),X
                    {
                        Seqstackpop(S, top); // 父节点出栈
                        Seqstackpush(S, i, s1, top); // 右子树入栈
                    }
                    else//即：(A,X
                    {
                        Seqstackpop(S, top);//左子树剩余元素出栈
                        top--;
                        Seqstackpop(S, top);         // 父节点出栈
                        Seqstackpush(S, i, s1, top); // 右子树入栈
                    }
                    
                }
            }
        }
       
    }
    return 0;
}


*/


/*本地正确，学习通第二组数据会超时
#include <iostream>
#include <stack>
#include <cstdio>
#define MAXSIZE 1000
using namespace std;
typedef struct BiTnode 
{
	char data;
	struct BiTnode *lchild, *rchild;
}BitNode,*BiTree;
BiTree createBiTree(char *s)
{
	BiTree T;
	T = NULL;
    stack<BiTree> S;
	BiTree p = NULL;
	int k = 0, i = 0;//k=1表示左孩子，k=2表示右孩子
	char ch;
	ch = s[i];
	while (ch!='\0')//ch一个一个读取广义表字符串
	{
		switch(ch)
		{
		case '(':
			S.push(p);//遇到左括号，接下来读取的元素可能是左孩子，将双亲结点p入栈，标志k为1
			k = 1;
			break;
        case ',':
            k = 2; // 遇到逗号，下一个读取的元素是右孩子，标志k为2
			break;
        case ')':
            S.pop();//遇到右括号，表明当前层读取结束，回退到上一层，上一层的栈元素将成为新的双亲结点
			break;
		default://遇到字符，创建新结点，将该结点插入对应的子树中,k=1表示左子树，k=2表示右子树
			p = new BitNode;
			p->data = ch;
			p->lchild = p->rchild = NULL;
			if(T==NULL)
			{
				T = p;
			} 
			else if(!S.empty())
			{
				switch(k)
				{
				case 1:
					S.top()->lchild = p;
					break;
				case 2:
					S.top()->rchild = p;
					break;
				}
			}
			break;
		}
        i++;
        ch = s[i];
	}
	return T;
}

void output(BiTree T)//中序输出树
{
    if(T)
    {
        output(T->lchild);//先左孩子
        cout << T->data<<' ';//中序
        output(T->rchild);//后右孩子   
    }
}

int main()
{
	char str[MAXSIZE];
	BiTree T;
	T = NULL;
	gets(str);
	T=createBiTree(str);
	cout << "二叉树中序遍历:";
	output(T);
	return 0;
}
*/
